m COMPLEXITY MEASURES FOR PROGRAMMING LANGUAGES Technical Memorandum 17 (This report was reproduced from an M.S. Thesis, MIT, Dept. of Electrical Engineering, September 1971.) Leonard I. Goodman September 1971 PROJECT MAC Massachusetts Institute of Technology- Cambridge Massachusetts 02139 ACKNOWLEDGEMENTS I wish to thank Professor John Donovan, the supervisor of this thesis, for his encouragement, enthusiasm, and guidance during the research and preparation of this report. His help is deeply appreciated, I acknowledge fellow graduate student Jerry Johnson for the many discussions we had during the early formulation of this work, and Cathy Doyle for her typing of this thesis report. Finally, I thank my wife Hindi for her patience and encour- agement during my graduate study. Work reported herein was supported in part by Project MAC, an M. I. T. research program sponsored by the Advanced Research Projects Agency, Department of Defense, under Office of Naval Research Contract Number Nonr-4102 (01). Reproduction of this document, in whole or in part, is permitted for any purpose of the United States government. COMPLEXITY MEASURES FOR PROGRAMMING LANGUAGES* Leonard I . Goodman Abstract A theory of complexity is developed for algorithms imple- mented in typical programming languages. The complexity of a program may be interpreted in many different ways; a method for measuring a specific type of complexity is a complexity measure -- some function of the amount of a particular resource used by a program in processing an input. Typical resources would be execution time, core, I/O devices, and channels. Any resource whose use is independent of previous and future usage can be handled by the theory. This condition includes time but excludes space complexity. For a specific measure, the com- plexity of the basic programming elements can be determined and used to compute the complexity of an arbitrary program with a particular input. Because this method gives little information about the general complexity behavior of the program, another approach is developed. This new approach analyzes the complexity of a program with respect to a valid set of inputs -- a finite set of legitimate, halting inputs. A program equation is developed to make the trans- formations undergone by the inputs more explicit. Using the equa- tion, the input set is partitioned into classes of constant com- plexity. The classes are used to compute maximum, minimum, and expected complexities of the program on the input set. Several equivalence relations are defined, relating different programs by their complexity. Complexity is also discussed in terms of concatenation and functional equivalence of programs. *This report reproduces a thesis of the same title submitted to the Department of Electrical Engineering, Massachusetts Institute of Technology, in partial fulfillment of the requirements for the degree of Master of Science, September 1971. Table of Contents Chapter I - Introduction 6 1. Functions^ Algorithms, Programs 7 2. Complexity Measures 9 3. Previous Work 10 4. Graph >k)dels of Programs 11 Chapter II - Complexity of Arbitrary Programs for Single Inputs 13 1. Introduction 13 2. Constraints on Complexity Measures 13 3. Complexity of Basic Program Elements 15 4. Complexity of Arbitrary Programs 22 5. The Set Approach 23 Chapter III - Program Equations and Set Complexity 24 1. Introduction 24 2. Input Sets 24 3. Program Equations 25 4. Complexity Equivalence Classes 31 5. Conclusion of Example Program 35 6. Summary 37 Chapter IV - Complexity of Advanced Constructs and Input Schemes 38 1. Introduction 38 2. Subroutine and Function Calls 38 3. LOOP Blocks 44 4. Multiple Inputs 48 5. Different Data Types 51 6. String Input 52 Chapter V - Results in the Complexity Theory of Programming Languages 53 1. Introduction 5 3 2. Preliminary Definitions 53 3. Relations Between Programs with Identical Input Sets 56 4. Concatenation 67 5. Functional Equivalence 73 Chapter VI - Conclusions and Suggestions for Further Study 76 Appendix - Mathematical Notation 80 References 84 -6- Chapter I. Introduction Within the past ten years^ there has been an increased interest by computer scientists and mathematicians in the theory of computational complexity. This theory is concerned with measuring the difficulty of computing functions and with studying the properties of measures of computational difficulty. Most of the work done in this field has remained within the domains of recursive function theory and the analysis of Turing machine computation of functions. (See, for example, Hartmanis and Hopcroft [1] for an overview of complexity theory.) One area of complexity theory that has not received much attention is the analysis of functions represented by computer programs. The current research is directed towards this area. We attempt to apply the basic principles of computa- tional complexity theory to algorithms which are Implemented In typical programming languages. One of the basic ideas of this complexity theory of programming languages Is to view the complexity behavior of a program over a finite set of 'Valid Inputs", rather than over some infinite domain or for only one Input. A 'Valid Input" Is one for which the program in question halts and which the program is actually intended to process. Looking at the complexity for all the elements in a set of this type will enable us to get a better picture of the complexity behavior of the program. We will also be able to define some relationships between different programs if the complexities of their elements relate in certain ways, 1. Functions, Algorithms, Programs We have mentioned the concept of computational complex- ity with regard to functions^ algorithms, and programs without clearly defining these three terms and explaining the differences between them. A function defines an association between the objects of one set (the domain of the function) and the objects of another set (the range). The method of determining the object in the range set corresponding to the object in the domain need not be explicitly stated; a set of ordered pairs of the form (domain element, range element) completely defines a function. Even if a rule for the function is given (e.g., via a lambda expression [2]) the evaluation of the rule may remain indeterminate. For example, if we have the function \x. x^fx*x do we perform the addition first or the multiplication? The computational complexity of a function would have to measure the difficulty of computing the range element given a domain element, no matter what rule was used to determine the range element (more than one rule may specify the same function), or how the rule was evaluated (as long as the evalua- tion procedure produced the correct answer). Complexity theory of functions is outside of the current discourse. -8- An algorithm is either the specification of the rule which defines a function and the method for evaluating the rule, or simply the evaluation procedure for a given rule. An algorithm is frequently presented in terms of a flow chart, where each of the nodes of the chart represents a basic operation whose meaning and evaluation are (hopefully!) unambiguous. The complexity of an algorithm is more basic than that of a function. In the case of an algorithm, we need only examine the specific evaluation procedure defined by the algorithm in order to determine the complexity behavior we wish to observe. However, in our complexity analysis, we will eventually come down to analyzing the basic elements of the algorithm: arithmetic operations, assignments of values to variables, testing condi- tions, branching, etc. The complexity of these simple operations generally cannot be specified any further. We may choose to express these operations in terms of the corresponding Turing machine operations and deal with Turing complexity. Although this may be adequate in some cases, the complexity of an algorithm on a Turing machine does not give much Insight into the complexity of the same algorithm written in a programming language and run on a computer. A program is the Implementation of an algorithm In a particular programming language. If the program is written in the assembly language of a particular machine, we can determine the complexity of the basic elements of the programs in terms of -9- the characteristics of that machine. If the program is written in a high-level language^ the complexity properties of the basic operations would not be completely constrained until we specify which machine the program will run on (and probably how the language translator to be used on the program would work). How- ever^ we may choose to leave the complexity in terms of the basic operations of the high-level language. 2. Complexity Measures The computational complexity of a program may be inter- preted in many different ways. A scheme for measuring a specific t3^e of complexity will be called a complexity measure . Basically, a complexity measure is some function of the amount of a partic- ular resource used by a program as it processes a specific input value. This resource might be time, space, CPU usage, channel activity, etc. We might have a program with input n. Asso- ciated with is a measuring program $ which is 'faonltoring" the execution of 0, $(n) would tell us the amount of a particular resource used by to compute 0(n). Thus the program $ is mea- suring the complexity of 0. In the recursive function formulation of complexity theory, a complexity measure is a recursive enumeration of all partial recursive functions , to each of which is associated a step-counting function $.. f. is constrained to satisfy the following two axioms (from Blum [3]): 1. 0^(n) is defined iff $^(n) defined -10- 2, M(i^n,in) = JO if $^(n) ^m is a recursive function I 1 if $^(n) = m By defined, we mean that a function halts for a particular input. Uses of Complexity Measures As we have stated, a complexity measure provides infor- mation on the resource usage of a program. As long as programmers have been writing computer programs, they have been concerned with the resource usage of their programs; specifically, they have wanted to know how long their programs would run and how much core they would require. As multlprocessed and time-shared computer systems evolved, programmers wanted to know about the use of system resources other than CPU time and core: channel usage, device usage, secondary storage requirements, supervisor usage, etc. The amount of each of these resources used by a program would constitute a different measure of Its complexity. A theory of computational complexity would give us a method for quantitatively analyzing the complexity behavior of computer programs and for comparing different programs on the basis of this behavior. Hopefully, this theory should be some- what independent of which type of complexity is being measured, so that the same techniques would be suitable for a number of different resources. 3. Previous Work There has been little work done in the area of complex- ity measures for programming languages. Meyer and Ritchie [4] -11- found some weak bounds on the running time of a class of pro- grams called Loop Programs. These programs compute exactly the primitive recursive functions. However^ programs written in most languages will compute recursive functions which are not primitive recursive. Thus, the Loop Program analysis is not general enough. Ramamoorthy [5] studied the time complexity of programs which could be modelled by discrete Markov processes: each decision-making element in the program is statistically indepen- dent of all others. He felt that his analysis would be useful for micro-programmed instruction sequences. However, the tech- niques developed would not work in the case of an arbitrary program. 4. Graph Model of Programs We will be using the graph model to represent the structure of computer programs. We present here an informal definition of this model. A graph of a program consists of a set of nodes connected by a set of directed arcs . The nodes represent the statements or elements of the program; they will be labelled with a statement identifier or function name. The arcs represent the flow of control in the program. They determine the execution sequence of the nodes. More than one arc may leave a particular node. In this case, each arc will be labelled with a unique selector that determines which node will be executed next. -12- ^ successor of a given node is a node which is pointed to by a directed arc from the given node. A predecessor of a given node is a node which points to the given node. A node may precede or succeed itself. A node with no arcs leaving it is a terminal node ; it is the last node to be executed. A program graph may have more than one terminal node. The node which is pointed to by an arc that has no node at its other end is the starting node . A graph may have only one such node. The arc leading into the starting node may have an input value or set of values at its other end. The entire graph will usually be labelled with the name of the program. ThuSj the program A consisting of the statements Sj^, s , 3^ where a^ is a conditional statement with two possible successors would be represented as : A: X X is the input value; s is the starting node, s is the terminal node. The successors of s^ are s and s^; the predecessor of s is s . T and F are selectors for s -13- Chapter II. Complexity of Arbitrary Programs for Single Inputs 1* Introduction Before we analyze the complexity behavior of programs over a set of inputs, we will first present methods for determining the complexity of a program with respect to one input. This will involve defining the complexity of the basic programming constructs to be used in the programs, and specifying a set. of rules which will enable us to compute the complexity of a group of basic con- structs which have been combined. These rules will determine the types of complexity measures for which our methods and techniques will be valid. It happens that these same rules will be suffi- cient for analyzing complexity behavior over a set of inputs, 2. Constraints on Complexity Measures We will require that our measures of complexity satisfy three rules. The first two rules are the axioms of Blum presented in Chapter I, The first axiom, 0.(n) defined Iff i (n) defined, implies that the measuring function (program) $. must depend on the entire computation of 0. on Input n; if this were not true, then $ might produce an answer even though did not halt. This axiom also Implies that when 0. terminates, we have all the neces- sary Information to determine the complexity. The second axiom, M(l,njm) = To if $ . (n) ^ m is a recursive function Co if $^(n) ^ m is Ll if $^(n) = m states that we can always tell if operating on input n will have -14- complexity m. In the case of time complexity we could let our pro- gram 0^ with input n run until it had executed for m time units. If 0^ halted, M(i,njm) = 1. If continued to execute, M(i,n,m) = 0. The third rule is the linearity constraint . It is this rule which allows us to find the complexity of a group of basic ele- ments which are formed into a structured program. The constraint may be stated as follows: Let A be a program with input x, such that A can be divided into two segments s and s where s is the predecessor of S2. A graph for A would be: A: We can represent the complexity of A with input x as C(A,x). Simi- larly the complexity of s- is C(s ,x). However, s does not have input X but rather some transformation upon x, induced by s • We can represent the input to s^ as s-(x). The complexity of s^ is then C(s2>s-(x)). Linearity requires that for all x for which A halts, C(A,x) = C(s^,x) + C(s2,s^(x)) Another way to state the linearity constraint is that any use of the resource in question must be independent of how much was used previously or how much will be used in the future, but dependent upon transformations of the input. -15- Time of execution satisfies this constraint. Other resources which also do are the number of calls to the supervisor program, device usage, and channel usage (from the point of view of the number of times the channel is used). One resource that does not generally satisfy the constraint is the amount of core used by a program. Since core may be shared, it may be available for different uses at different times. In the previous example, some of the space needed for S2's computations may be done in s 's area. Thus, C(A,x) ^ C(s^,x) + C(s2,s^(x)) However, if space is never reused, then space complexity may be incorporated into the general theory. For any resource which obeys this constraint, the methods to be presented may be used to deter- mine the complexity of a program with regard to the use of that resource. 3. Complexity of Basic Program Elements Our goal is to be able to determine the complexity of an arbitrarily structured program. First, we will define the com- plexity of the basic elements of our language. This language will not be any specific one but will be representative of modem high-level languages. Below, we list one possible set of basic elements. Naturally, we cannot include every possible program construct; however, those listed are found In many languages. Arithmetic operations Assignment -16- Transfer of control Conditionals Iteration Function calls I/O and supervisor calls In discussing each of these elements^ we will use time as a sample resource. Of course^ "time" may be expressed in micro- seconds, GPU cycles, or any other units. Other complexity measures may be handled similarly. Arithmetic Operations This category includes the common mathematical opera- tions. The time complexity of any of these operations is just the time required to execute it. If we are dealing with an assembly or machine language program, we may express the time in terms of the instruction execution time of the corresponding machine. If we are writing in a high-level language, and if we know the computer which will execute the machine code resulting from our program, we may express the time complexity in a similar manner (ignoring any compiler optimization). If we do not know which machine will execute our program, we may choose to measure the complexity in terms of the number of additions, the number of multiplications, and the number of other independent operations. We may think of having an n-dimensional "complexity vector", where n is the number of independent opera- tions. The "unit vector" for each of the dimensions is the com- -17- plexity of a basic operation; the coefficient of this unit vector is the number of such operations which have occurred. We can reduce this vector only if we express the unit complexities in terms of something else^ such as the machine instruction times of a specific computer. Then we can obtain one value for the complexity^ as we did in the case of an assembly language program. Note that we are treating the complexity of these opera- tions as having a fixed value, independent of the value of the operands. If this assumption were not true, we would have to examine the sub-operations which form an operation until we found some con- structs which were complexity- invariant. We will need this condi- tion when we examine complexity for a set of inputs. Assignment; Transfer of Control By assignment, we mean the assigning of the value of one variable to another. Transfer of control is the familiar BRANCH or GOTO statement. These two constructs may be treated in the same way as the arithmetic operations: either their complexity may be expressed in terms of instruction execution time or they may be treated as two of the independent operations. We also assume that the complexity of these operations is a fixed value. Conditionals The prototype of our conditional statement will be: IF p(x) THEN 8^ ELSE S2 ■18- P is some test on the value of x which does not change this value. If this test is satisfied (p(x) TRUE), then s^ will be executed; otherwise S2 will be executed. We can represent the structure of the conditional by the following graph model: Using the linearity condition and noting that p does not change the value of x, the complexity of our conditional will be: l*x) = C(p,x) +|c(Sj^,x) LC(s2,x) C(cond,x) = C(p,x) +fc(B^,x) if p(x) TRUE if p(x) FALSE p, 8^, and S2 may all represent complex constructions, which can be broken down to basic elements. Iteration In most languages, the programmer has the ability to execute a section of program repeatedly, depending upon certain conditions. This Is the basis of the Iteration statement. We usually have a variable, defined only for the iteration construc- tion, whose value is incremented from a lower limit to some upper -19- limit while the statements within the bounds of the iteration state- ment (the body ) are executed for each increment of the variable. Some languages allow additional features: multiple ranges for the control variable, negative increments, negative lower limits, attaching a conditional test to the iteration, and others. Examples of the iteration construction are the FORTRAN DO statement, the ALGOL FOR statement, and the PL/l DO statement. We will use a particularly simple form of iteration state- ment. We will retain only the concept of executing a body of state- ments for a certain number of times. This is the LOOP block and has the following form: LOOP N {body} END The semantic interpretation of the LOOP block is that the body is executed N (contents of N) times in succession. Changes to N within the body do not affect the number of times that the body Is executed. The body may contain other LOOP blocks; thus they may be nested to any level. The complexity of a LOOP block may be interpreted in several ways. We may view the LOOP structure as equivalent to N physical copies of the body of the block. We may then compute the complexity using linearity. Alternatively, since the LOOP block is usually the feature of a high-level language, we may -20- examine its translation in machine langtiage. This will involve the initialization of a dummy variable, the body of the block, the incrementing of the variable, a test to see if we have exceeded the number of iterations, and a transfer to the beginning of the body. The complexity of the block could then be computed using the complexity of these elements and the linearity condition. We will use the simpler interpretation of complexity. If we denote the body of the LOOP block by s, and assume that all statements within s are a function of the variable x, then the LOOP block LOOP N s END will have complexity C(LOOP-BLOCK,x) = C(s,x) + G(s,s(x)) +C(s,s^(x)) + C(s,s^(x)) +...+ C(s,s^"\x)) where s denotes the functional composition of s with Itself i times. Function Calls A function or subroutine call involves a call to the subprogram executed in the calling program, and the execution of the subprogram itself. We will assime that the call state- ment is a basic construct similar to an arithmetic operation and -21- that its complexity is independent of its argument; furthermore, we will assume that it does not change the value of its argument. The value of the call statement argument , and hence the input to the subprogram, will be some transformation of the original input to the calling program. As an example, consider the program A with input x which contains a call to the function B with argument X (actually some transformation on the original value of x). A could be represented in graphical form as: The complexity of A would then be C(A,x) = C(Sj^,x) + C(GALL) + C(B,Sj^(x)) + C(S2, B«Sj^(x)) All occurances of x in this expression denote the original input value of X. I/O and Supervisor Calls We can view these constructs in the same light as arithmetic operations. For a particular machine, the time com- plexity of these elements is simply the time needed to execute them. In a high-level language, we may treat them as independent -22- operations. Types of Complexity Certain elements have a constant complexity which does not depend on their inputs. This group includes arithmetic opera- tions^ assignment^ transfer^ and the supervisor operations. Condi- tional statements have a constant complexity for those inputs for which p(x) is true^ and another constant complexity for those inputs for which p(x) is false. This assumes that the elements composing Pj s^ and s^ are all of constant complexity. Finally^ we have loop's and subroutine calls which have a complexity dependent upon the input and number of iterations for the LOOP block and the input for the subroutine or function. If certain supervisor operations have different complexi- ties for different inputs, we may treat them as subroutines. ^. Complexity of Arbitrary Programs Having defined the complexity of our basic programming constructs, we can use these complexities and the linearity condi- tion to find the complexity C(A,x) of any program A with any input X for which A halts. (We may easily extend our results to include the case of programs with multiple inputs. ) This approach, however, does have shortcomings. The complexity of a program with respect to one input will not usually give us much information about the general com- plexity behavior of the program. We will know even less if the program does not halt for that input. If we wish to learn more -23- about the complexity behavior, we will need to repeat our calcu- lations for a large set of inputs. Although the program may exhibit the same complexity behavior for many different inputs, we will not be able to take advantage of this relationship because we are dealing with each input individually. The domain of input values is arbitrarily large until we bind our program to a partic- ular machine or language specification. Because of the nature of this domain, we cannot bound the values of C(A,x) since A defines an arbitrary partial recursive function. Finally^ we have no facility for comparing the complexity behavior of two different programs other than inputting the same value to both programs and calculating the resultant complexity. 5. The Set Approach The remaining chapters will use the work on single input complexity to develop another approach to program complexity. This approach examines the complexity behavior of a program over a finite set of inputs which have certain useful properties. The set approach will make it easy to examine such behavior as the expected value of complexity and maximum and minimum complexity; the complexity structure of a program will become more apparent. Also, the set approach will enable us to examine complexity rela- tions between different programs. -24- Chapter III. Program Equations and Set Complexity !• Introduction Having defined the complexity of the basic program elements and developed methods for determining the complexity of a program with respect to one inputs we are ready to deal with program complexity with respect to a set of inputs. We develop the concepts of the program equation and a valid set of inputs to aid in the complexity analysis. We make some simplifying assumptions about the type and number of Inputs to our programs and the type of components in these programs. In the next chapter we remove these restrictions to obtain a more general model. An explanation of the mathematical notation used in this and later chapters will be found in the appendix. 2. Input Sets We will assume a simplified form of input structure for our programs. These programs will have only one input, which will be a non-negative Integer; further, we will assume that all operations upon this input result in non-negative Integer values. Given a program A which satisfies these conditions, let U- be the set of non-negative Integer Inputs for which A halts, and which are valid inputs to A. By a valid input, we mean an input which A Is actually Intended to process. Thus, if A is meant to process only even non-negative Integers, then U^ contains only these integers, though A may halt for some odd integers or, in fact, for all odd integers. -25- Next, let U2 be the set of allowable non-negative integer values for the machine on which A is running or for the language tn which A is written. (If both the language and the machine limit the set of values, we will use those conditions which are more restrictive.) V^ may be quite large, but it is always finite. We can now define a valid input set X to the program A as : X = u^n U2 We see that X is finite and for all inputs x in X, A halts. We may be interested in examining only some of the valid Inputs to A at any particular time. If X'OC, we will say that X* is also a valid input set to A. x' has the same properties as X except that it does not contain all the valid halting Inputs for A. We will refer to X as the maximal valid Input set to program A for a particular U2 - i.e., for a particular machine or language realization. 3. Program Equations We now define a method for obtaining an equation representation for a program. We will initially assume that the program contains no LOOP blocks or subroutine calls, and has only one input.- These restrictions will be removed later. The concept of a program equation is based on the work of Zeiger [6]. He derives some relationships between programs, polynomials, and power series. We start the derivation of -26- the equation by putting our program A into graphical represen- tation. With each node of the graph, we can associate a func- tion on the inputs to that node. Since we have temporarily eliminated LOOP's and subroutines, we have remaining arithmetic operators, assignment, transfer, conditionals, and supervisor calls. Transfer does not change any values. Assignment is a type of arithmetic operation, and supervisor calls change values of variables in specified ways. Thus, we have two general types of functions: arithmetic and conditional. An arithmetic function f maps a set X into another set F, defined as: F = f (X) = { f(x) I xeX } A conditional function p maps X into a set P. We will say that p(x) « X if X satisfies the predicate p; otherwise p(x) is undefined. Therefore, p acts as an identity function for those inputs which satisfy its associated conditional test. We can see that p(x) is defined if and only if p(x) = x. Then P = P(X) = { xeX I p(x) is defined } We are using the conditional function in a different sense than the conditional statement of the preceding chapter. That statement had the form IF p (x) THEN s ^ ELSE 82 ■27- p(x) is assumed to take either the value TRUE or FALSE. If p(x) = TRUE, we execute s^^; otherwise, we execute S2. In the case of a conditional function, we have the following situation; p(x) defined / \ p(x) defined We define the function p(x) as follows: p(x) defined iff p(x) undefined If p(x) is defined, its value is x; we take the arc with the appropriate selector and ezecute s- with input x. We cannot execute s^ because the selector leading to this node was not satisfied. Conversely, if p(x) is undefined, p(x) is defined; its value is x. We then execute s^ with input x. One case or the other (but not both) must happen. We also have the relation p(x) = p(x) so that if our conditional function is p(x), our selectors will remain the same. We will abbreviate ''pCx) defined'' by '*r" -28- (TRUE) and '^(x) defined" by ''F'' (FALSE). This is in keeping with the standard notation of program conditionals. Having specified the function associated with each node of the program graphs we define the equation of the pro- gram as the summation of all possible functional paths from the starting node of the graph to any terminal node, A func- tional path is defined as the composition of the functions associated with the nodes which comprise the path. The resulting composed function is applied to the set of inputs. The stun of chese functional applications is set equal to the function defined by the entire program applied to the set of inputs. Given a program A with input set X, its equation would be A(X) = Zf,(X) i=0 ^ where each f is a composition of simpler functions. The summation is of infinite extent because an arbitrary program graph contains an infinite number of paths. We illustrate these concepts with a sample program: A: -29- The simplest path through A starts at p and takes the F arc to the halting node. We will assume that this latter node has no functional or complexity significance. If we recall that F is equivalent to '^(x) defined", the first term of A(X) will be f q(X) = p(X) « { xeX I p(x) defined } The next simplest path starts at p, takes the T arc to g, returns to p, and then takes the F arc to the halting node. The composition of the functions encountered in this path is (with the right-most function encountered first) f j^ = P»g-P This function applied to X yields the next term of A(X): f^(X) ^ [ g(x) I xgX & p(x) defined & p(g(x)) defined ] Continuing In this manner we get the complete equation: A(X) »7(X) + P*g-p(X) + p.(g.p)^(X) + ... = Ep«(g«p)^(X) i«0 where (g»p) = the identity function. Xhsxe Is no unique corre- spondence between a particular index and a particular functional path. In this case, we have calculated functions in order of -30- increastng path length. It happened that f^ ^ P*(g'P) However, any other one-to-one correspondence between the f. and the functional paths would work. We will conclude this example later in the chapter. The application of f to X results in a set of values. We define F^ = f^(X) The 4-*s in our equation are to be interpreted as set union. Then F.C A(X) and U F^ = A(X) ^ i=0 ^ Each f Is generally composed of arithmetic and conditional functions. Suppose f . = g •...•g.. We will say that f.(x) Is defined If and only if for all conditional functions g €{ S^^g^.j* •••» gj^ }^ g. applied to its argxanent is defined; I.e., g.(g, , •. . . 'g, (x)) is defined. Then f^(x)€F^ if and only if f^(x) is defined. Now we can define the set of elements in X which exactly yield each F : X^ = [ xeX I f^(x) is defined } We then have the relation F = f.(X ), -31- Simplification of the Equation We can reduce our equation if we require that X be a valid input set to A. , We then have that X is finite and for all inputs in X^ A halts. Since X is finite, there are only a finite number of non-empty X . Let m be the greatest integer for which X ?^ (the empty set); then for all i>m, X =0 and F,=0. We then have: m 1. A(X) = Zf.<X) i=0 ^ ni 2. U X = X (it may be that some of the X are empty; i=0 ^ ^ this will occur if the corresponding F. is empty) 3. X nx =» if if^j (because programs are deterministic, any input undergoes only one trans- formation) 4. Each f is composed of only a finite number of sub- functions since A halts for all x in X. Thus, given a valid input set, we can reduce our program equa- tion to a finite number of terms, each term of finite extent. We also get a partition { Xq,X ,...,X } of our original input set. 4. Complexity Equivalence Classes The subsets of X, { X. }, have the following property: for all xeX., the functional path associated with x is the same. Since we have allowed no LOOP blocks or subroutines in our programs, and since all x in X. take the same branch from every -32- conditional test, the complexity of this functional path is con- stant. This complexity is completely defined in terns of the functions in the path and has a value C(A,x)j xcX . X will be called a complexity equivalence class . Associated with each X. will be an equivalence class complexity * C(A,X. ), By definition. C(A,X^) = C(A,x), xgX^ The complexity information for program A with input set X is contained in the two sets { Xq,X^,...,X^ } { C(A,X ), C(A,X.),_.,C(A,X ) } u i m We observe that many programs do not treat every input differently. Often, many inputs will be similarly processed. Therefore, we are led to believe that the number of equivalence class will often be smaller (though not always much smaller) than the number of distinct input values. In this case, we have a (rela- tively) compact description of the complexity behavior of A. Uses of Complexity Equivalence Classes The complexity equivalence classes may be used to calculate the following quantities with respect to a particular input set: 1. Expected value of complexity -33- 2. Maximum value of complexity 3. Minimum value of complexity In a later chapter we will show how these classes are useful in determining relations between different programs. Expected Complexity Value Expected complexity value will tell us the average resource usage by a program over a particular input set. The expected value of a function g over a discrete-valued domain X is (see, for example, Drake [7]) the sum of the products of values of the function at points in the domain and the prob- ability that the particular point will be chosen: E(g,X) = s g(x).Pr(x) xeX If C(A,X) is the expected value of the complexity of A with input set X, C(A,X) « E C(A,x).Pr(x) xeX m Since U X « X, i«0 ^ C(A,X) - E S C(A,x).Pr(x) X^xeX^ But for all xgX^, C(A,x) = C(A,xp; and since x^cX^ and x^eX^ are independent events. Pr(X ) = S Pr(x) xeX^ ■34- Th en. S C(A,x).Pr(x) = r C(A,X,).Pr(x) xeX^ xeX. C(A,X^)(2 Pr(x)) = C(A,X^).Pr(X^) xeX^ /. C(A,X) = E C(A,X )-Pr(X ) The probabilities Fr(X.) are based on any method used in selecting the inputs to A, and take into account any 1 P^^-o^^^ knowledge of the selection method. If the selection of inputs is random, Pr(xp » I X^ |/| X If X. « 0, then for any selection method, Pr(0) « 0. The value of C(A,X) is not changed by averaging over empty sets. Maximum Value of Complexity The maximtm complexity is an upper limit on the usage of a particular resource for any execution of a program, given an input value from the input set in question. To compute this quantity, we need only find the maximum value of C(A,X. ) over the X . We must remember that some X may be empty; so we only look at C(A,X ) for non-empty X.. The maximum com- plexity will be denoted C (A,X). ■35" Minimum Value of Complexity The minimum complexity is the corresponding lower limit of resource usage by the program. It is the minimum of C(A,X.) over the non-empty X,. It will be denoted C (A,X) ^ min ^max^^^^-^ ^"^ ^min^^'^^ ^^^ important quantities. They say that any execution of the program will require C CA^X) of min^ ^ ^ resources, but never more than C ^ (A,X), when inputs are taken max from X. 5. Conclusion of Example Program Returning to our sample program introduced earlier in this chapter, we will specify the input set and the functions com- prising the program: X= { 1,2,3,. ..,10 } g(x): x:=2lc (x is assigned the value 2x) p(x) = X iff xfi5 p(x) = X iff x>5 A(X) = E f (X) 1=0 ^ — — — 2 fo "" P ^1 " P*(g'P) ^2 " P*(S'P) - • • ^0 " ^0^^^ = { xeX I 7(x) is defined } = [ 6,7,8,9,10 } Xq = f 6,7,8,9,10 } F^ = f^(X) = p([ 2,4,6,8,10 }) = { 6,8,10 } X^ = { 3,4,5 } .^-S*^-^;^ -36- Fj - fjCX) -?({ 4,8 }>*{ 8 3 :. ax-,» X ;. ;. (Vna4) [F^- X^- 0] ;. A(X) - i£,(X) 1-0 * i'Sii',, ■ '-'-O ;• • P<^M?^^»>f «eXQ X v\t-^-:-^-'':^^*<^'-^r-^^.Cr ''■;;'3b.;>; Nota thftt eh« conplaxlty of the conditional tMt (p lt»«lf) 10 eh« MM i»h«eher p(x) or p(x) U A^tis^^ ttmt^rm. C(p>x) - C(p,x) - c , VxeX P C(A,Xj^) - C(A,x), xeX^ C(A,x) - C(p,ae>i^^(i;fc>4 C(?,g(k» c + c_ + c « 2 c + c .^ ,^ . V K:>{ilisrj :.F ;; ^)? ■; A'>-^. C(A,X^) - 3Cp + 2Cg C<A,X-) - 4c + 3c i 'Ol'l%?^S,,,?t.d ■| ■*«'^Jt •37- To determine C(A,X)^ the expected complexity^ we need to know the values of Pr(X^). Let us assume a random distribution. Then Pr(X^) = I Xj/| X I C(A,X) = i C(A,X,).Pr(X.) = i=0 ^ ^ 5 c +3 (2c +c ) + 1 (3c +2c ) + 1 (4c +3c ) loPIo PS loPS loPg = 9 c + 4 c 5 P 5 8 Cmax<^'X> = C<A,X3) = Uc^ + 3Cg 6. Suranary We have developed several important concepts for the complexity study of programs - valid input sets, an equation representation of a program, complexity equivalence classes, and equivalence class complexities. We have seen the use of these concepts in the analysis of complexity behavior. Finally, we have shown how the equivalence classes and their associated complexities have given a compact and orderly representation of the complexity information for a program over a set of Inputs, ■38- Chapter IV. Complexity of Advanced Constructs and Input Schemes 1. Introduction In this chapter we extend our complexity analysis pro- cedures to include programs with additional programming features, such as subroutine calls and LOOP blocks, and also programs with more than one input. We also discuss input data types other than the non-negative integers and finally variable length inputs. 2. Subroutine and Function Calls Let us assume that we have a program A with valid input set X. A has the finite equation representation A(X) ^If. (X) i=0 ^ We can express the j term, f ^ as a composition of subf unctions: Suppose g. is a call to the program B. Let Y be the maximal valid input set to B. The equation for B Is then B(Y) = S h.(Y) 1=0 ^ B will be called from A at point g. within f . with a set of values X' = gj^.....g^(X) -39- where the series of composed functions is the transformation applied to the elements of X, If we assume that A is working correctly, then all values passed from A will be valid inputs to B. Thus X'c Y. The equation for B(X') will have, at most, as many terms as that for B(Y). Then q B(X') = Sh (X'), qsp i=0 ^ To obtain the complexity equivalence classes for A with input set X, we cannot simply calculate the X corresponding to the F- = f . (X). The reason is that there is no unique complexity associated with X since f contains a call to B which has q-fl distinct functional paths associated with it. To get the true equivalence classes for A, we will have to substitute the terms of B(X*) into A(X) between g- - and g in f . Assuming no other function calls in A, this procedure will yield an expanded set of functions f *, each having a unique functional path. Any value It computed in B and returned to A will be available to gi^. n* This expansion yields the following equation for A: J-1 q A(X) o Sf.(X) + g„'...gv.i*( Sh ).g .....g (X) + 1=.0 ^ ° '^^^ 1=0 n+<i+l I f fx) = rf/(x) l=j+l ^ 1=0 ^ -40- We can now calculate the complexity equivalence classes X^ = { xeX I f^'(x) is defined } and the associated class complexities C(A,X ). We are assured of finding a new finite representation for A(X) because: 1. A(X) (unexpanded) has a finite number of terms. 2. B(Y) has a finite number of terms. 3. A is assumed to be operating correctly so that X'c Y. Therefore, B(X') has a finite representation. Intro- ducing B(X') into A(X) yields a new finite representa- tion for A(X). This method is general enough to handle multiple lavels of subroutine calls, multiple calls to the same subroutine from the same calling program, and recursive subroutine calls. To Illustrate multiple levels of calls, suppose that in the pre- vious example, B called a program C with input set y'. We would find the equation for C(Y'), substitute this into B(X'), and sub- stitute the expanded B(X') into A(X), We know that the process of subroutine calls must terminate since A halts for all input values in X. For the case of multiple calls from the same program, assume A called B twice, once with input set X' and once with set X". We would use our analysis procedure to find B(X*) and B(X") and sub- stitute these into A(X). -41- Suppose A calls itself as a subroutine. These recur- sive calls must terminate because of the halting condition. If the set of values passed from A to itself is X'^ we know that X'g X. After finding A(X'), we substitute it into A(X). Example of Subroutine Call We will consider a program A with input set X which calls a program B with maximal input set Y, A: X = { 1,2,3, ...,9 } p(x)=x iff x^ mod 3 g(x): x:«x+l ■42- Y = { 3,6,9,12,15, ...,3.n } h(y): y:=y/3 <i(y)='y iff y=o mod 3 Denoting the node "CALL B(x)" by "b", we have the following equations : A(X) - b.p(X) + b.p.g.p(X) + b.p.(g.7)^(X) + ... - E f . (X) 1-0 ^ B(Y) - q.h(Y) + q.h.q.h(Y) + q.h.(q.h)^(Y) + ... -Eh. (Y) 1-0 ^ Using our analysis on just the equation for A(X), we get the following classes; Xq = [ 3,6,9} X^ = C 2,5,8 } Xg - { 1,4,7 } A(X) = !: f , (X) 1=0 ^ -43- However, since the inputs in any X. undergo different transforma- tions in B, these are not complexity equivalence classes. We will have to substitute B(X') into A(X) wherever B is called from A. Let Xl be the set of inputs to B when B is called from fp. Then X^ = b.p(X) = { 3,6,9 } C Y Ho=hQ(X')= { 1,2 } x;^= [3,6 } Since X' = X'^ U X^^. B(XJ) = ShjX') = q.h(Xj) + q.h.q.h(X^) Similarly, let XJ be the set of Inputs to B when it is called from within the function f ^. Then, x; = f^(X) = C 3,6,9 } = X^ B(X') = ih (x;) 1 1=0 ^ ^ Finally we let XJ be the Inputs to B when it is called from f . X^ = f2(X) = [ 3,6,9 3 = X' B(X:) = ih (X') 1=0 ^ "^ -44- We can now substitute the three equations for B into the appropriate places in A(X) to get the expanded version of this equation: A(X) = B(Xj;).fo(X) + B(X{).f^(X) + B(X^).f2(X) = hQ.fQ(X) + h^.fQ(X) + hQ.f j^(X) + h^.f^(X) + hQ-f2(X) + h^.f2(X) 5 = Ef;(x) i=0 "■ Each of the classes X., i=0, 1,...5, now corresponds to a set of inputs with a single complexity value; each X is a complexity equivalence class. 3. LOOP Blocks We have discussed the LOOP block in a previous chapter and defined the complexity of this construction as follows: If the body of the block is denoted by s and all state- ments within s are a function of x, then the I/X)P block LOOP N 8 END will have complexity C(s,x) + C(s,s(x)) + C(s,s (x)) + ... + G(s,s " (x)) Ue can now include LOOP's into our theory of program equations and complexity equivalence classes. We will illustrate the -45- handllng of loops by several examples. Suppose we have the following program A with input x: LOOP X h(x) g(x) END If A has a valid input set X, we may represent A in graph format as follows: r _x ^ i halt The dotted lines delineate the scope of the LOOP block. The '*x" just outside the box defines x as the iteration control variable. The equation for A(X) will have to indicate that g and h will be executed a different number of times for each value of ■y '^.■-"■.■■-:5Tf?^^:|^, •46- X In X. Asstxmtng no attributable coiaplcxlty to^ND", the equation is A<X) « Z (g*hr(X) xeX If |x|«n, this sum will expand to h terms. If g and h have a constant associated complexity^ there will be n complexity equiva- lence classes for A witii set X, In this case. X^ » { x^ 3 *i»d C(A,X^) « C(A,x^) Let us consider the more complicated program B: ■^ ^^^^/^T» '■: -* ^W*- -* "^i^ : ^,;f-'- - U'-I m^l '\: j ^■■r i-' .1. ^^T ,}V*.- * --^i, halt -47- Now the LOOP block may be executed many times, the number of Iterations each time (i.e., x) dependent upon previous executions. To calculate B(X) we use our basic method: find those inputs for which B halts on the first pass through p, on the second pass, etc. Sum these terms to get B(X). If fp is the functional path which terminates on the first path through p, fo(X) = ?.E (g»h)''(X) xeX Similarly, if f . denotes the functional path which ends on the second pass through p, f,(X)-p.j: (g»h)* .p.s (g»h)^(X) x'eX' xcX X' Continuing in this manner. B(X) » E f, (X) i-0 ^ Since X is finite, there exists an n such that for all l>||^ fj^(X) - 0. .'. B(X) = S f,(X) 1=0 ^ ■48- While this is a valid equation for B(X), each X. = { xgX I f.(x) is defined } does not correspond to a single value of complexity. Each f, will have to be subdivided by expanding out the summations. The subterms, f!, will correspond to single values of complexity; and the X,, X^ = { xeX I f |(x) is defined } will be complexity equivalence classes, 4, Multiple Inputs We now extend our complexity analysis procedures to programs with more than one input. We will deal specifically with the case of two inputs. The generalization to programs with n inputs is immediate. Let A be a program with two inputs, x and y. Analagous to the one input case, we define the set U. as U, = { (x,y) I A halts for non-neg. integer inputs x and y; x and y valid } We then define U^ as the set of all ordered pairs of non-negative integer values for the language in which A is written or the machine on which A is running: U^ = [ (x,y) ] X and y are allowable non-neg. integer values } -49- Then the maximal valid input set to program A is z = Uj_nu2 As before Z'c Z is also a valid input set. We can then proceed to find the functional paths of the program graph from the starting node to a terminal node. The function f associated with each path maps ordered pairs (x,y) to (x*,y'). f is composed of arithmetic and conditional func- tions. For any (x^y)eZ, we can calculate a complexity C(A, (x,y)) defined by a path through A. Using the functional paths through A and noting that Z is a valid input set we can obtain the finite equation for A(Z)2 A(Z) = Ef.CZ) i«0 ^ The f . Imnediately lead to the complexity equivalence classes \ = { (x,y)eZ I f ((x,y)) is defined ) and the equivalence class complexities C(A,Zj^) = C(A,(x,y)), (x,y)eZ^ Before finding the Z , we may have had to expand the f to take care of any function calls or LOOP blocks. We can now calculate C(A,Z), C ^ (A,Z), and C (A,Z) as before, max tnin -5 0- If we define the sets X and Y as X = [x|ay such that (x,y)eZ} Y = {y|3x such that (x^y)£Z} we can easily see that Zc XxY. For (x,y)cZ implies that xeX and yeY which imply that (Xjy)eXxY. Note that Z is not necessarily equal to XxY. If, for inputs x^eX, ^o^^^ "^ does not halt, then (x^^yg)^ z. Inputs vs. Variables Although A may have n inputs, it may have m variables (including input variables) internal to it, in>n. One way to handle the m-n variables which are not inputs is to express them in terms of transformations on the inputs. Thus if y is not an input variable, then before it is used, it must have a value assigned to it. This value is a function of the n-tuple of input values: y = f((Xj^, ...,x^)) Another way to solve the problem is to view A as having m inputs. Those variables which are not actual Inputs have a default value assigned to them, say zero. If A is working correctly, these variables will be assigned new values before they are used for their original default values. -51- 5. Different Data Types So far, we have limited our discussion to programs which operate on non-negative integers from to intmax - an upper bound imposed by either the language in which A is written or the machine on which A is running. It is not conceptually difficult to extend the complexity analysis procedure to cover other types of input. In most implementations, negative integers range from -1 to some lower limit: negmax . If we wish to analyze a program A with an integer input (positive or negative), then our maximal valid input set X would still be defined as U-nU2> but now U- = {x| A(x) halts and x a valid integer input} U« - {x| X an integer and negmax s x ^ intmax } We would then procede as before to find the program equation A(X), the complexity equivalence classes X , and the subset complexities C(A,X. ). We may also easily handle character input (the character set on a machine is always finite) and floating point numbers (always finite in number because of the limitations on the magni- tude of the exponent and the precision of the fraction). In the most general case, we would have a program with several inputs of different data types. The work on multiple inputs would apply here^ generalizing to n-tuples with components of different data types. -52- 6. String Input We have not yet considered programs which have string or variable length input sequences. An example of such a program would be a compiler whose input is a series of characters in the source language which it is required to translate. There is often only one input variable in such programs; each time a new character is read, the value of that character is placed in the input variable. However, unlike previous programs where current values of variables could be defined in terns of transformations upon older values, the new value of the input variable in the case of string input is not generally definable in terms of previous values. Although we might like to treat this new value as a separate input, the number of such new inputs is indeterminate, so we cannot directly apply our previous methods. One way out of this problem is to observe that compilers and similar programs usually read their string of inputs until the string is exhausted. Therefore, given an input string of n charac- ters, we know that the program processing this string will read in n distinct input values. If we view an n character string as being n inputs to the program, then each length string defines a diff- erent input situation. Thus, when analyzing the complexity of a program with string input (where the string is always read in its entirety), a set of valid inputs would be defined as a subset of all strings of a fixed length, say n. We would then treat the program as having n inputs. -53" Chapter V. Results in the Complexity Theory of Programming Languages 1. Introduction We are now ready to investigate some of the proper- ties of the complexity-theoretic concepts previously intro- duced. We define some complexity relations between programs, define the complexity of concatenated programs, and study equivalence of programs in the light of complexity theory. We prove some results about these areas. 2. Preliminary Definitions We first define a special form of the complexity equivalence classes of a program; this form will be used in most of the definitions which follow. It is a standard which will be used in comparing equivalence classes of different pro- grams. Definition ; Given a program A with input set X, we define the set X. as follows: A X. »« f X, I X, is a complexity equivalence class A ** 1 ' 1 of A with input set X) (VX^eX^) Definitio n; X. is said to be in normal form iff — — — A ' ' ' ' ' ' ■ ■ " [X^7^0 (empty set) and i^^j ^ C(A,X^ VC(A,X,) ] .54- Normal form implies that all the complexity equivalence classes X^ contain at least one element of X and the complexity of any equivalence class^ C(A,X. )^ is unique. It is this normal form which allows us to compare the set of all equiva- lence classes of two different programs. If X^ is not in normal form, it may be put in this form by deleting any X^= 0, and if C(A,X^) = C(A,X.), then replacing X and X. by a new equivalence class X = X U X. where C(AjX^.) = C(A,X^). Note that the deletion of X = or the creation of X does not change C (A,X), or C . (A,X), or *-J max min C(A^X). In the case of G(A,X), we have X^= -> Pr(X^) = Also if we form X = X U X., then since X fl X = 0, Pr(X^j) = Pr(X^) + Pr(X^) ;. C(A,X^) • Pr(X^) + C(A,Xj) . Pr(X.) - C(A,X^j) . (Pr(X^) + Pr(X^)) = C(A,X^^) . Pr(X_) If we replace X and X. by X ,, C(A,X) remalas the same* Next we define a shorthand notation for the complexity equivalence of single inputs and equivalence classes of inputs. ■55- Deflnition ; Given a program A, the relation = is defined as follows: For K^, x^ valid inputs to A, x = X2 iff C(A,x ) = C(A,X2) For X., X. equivalence classes of A, X = X. iff J 1 A i C(A,X^) = C(A,XJ It is easy to see that = is an equivalence relation (reflexive^ symmetric, transitive) since it is defined in terms of another equivalence relation (=). Lemma 1 ; If X. is in normal form and x-^x^gX, then Xj^«=^X2 iff (a unique X^eX^ such that x ,x eX ) Proof: (<?.) Xj^,X2cX^-> C(A,Xj^) = C(A,X2) •♦ \=^^2 (">) Xi=A^2"* ^(^^^1^ ^ C(A,X2). Suppose Xj^eX and x^eX^. Then X =^Xj^. By normality of X^, ^f\^ Then Xj^,X2eXo X.eX . Since the X are disjoint, X. is unique. QED The lemma gives us another statement of the normal form condition - all inputs with the same associated complexity are in the same equivalence class. This result will be useful in later sections. -56- 3. Relations Between Programs with Identical Input Sets We now turn to relations between programs which have the same valid input set.. We will develop a series of equiva- lence relations between such programs, based on different com- plexity properties of the programs. Similarity The first equivalence relation, which we now define, is also the weakest. It specifies a relation between programs which divide the same input set into the same complexity equivalence classes. Definition ; Given programs A and B, both with input set X and with X. and IL in normal form, A and B are similar on X iff X^«Xg. Similarity between two programs on a given input set is equivalent to saying that two inputs to one program have the same complexity if and only if they have the complexity when input to the other program. This may be formally stated in the following theorem: Theorem 1 ; A and B are similar on X iff (VXj^,X2eX)IXj^=^X2<?=> ^"^^^2^ ■57- Proof: (=>) Suppose ^-^"=^^^2' "^^^^ ^^ lemma 1, x^jX^e X^j X^G X^ where X^ is in normal form. But by similarity^ ^A^'^B' ^^^" ^i^ ^B* Therefore, ^-^=^^2' ^^^^ewise, ^i=^^2^> ^rA^2' (<r=) Construct X. £ X from all xeX such that X =^x ; similarly construct X ! e X^ from all xeX such that x = x . ^ i- i B B i Since x =^x^ iff x ^^x^^^, X^= X_J. Continuing for all x eX, we see that X^e X^ iff X^e X^. Thus X^= X^. None of the X are empty (because = and = are reflexive); if C(A,X. ) = C(A,X.), then by hypothesis C(B,X ) - C(B,X ). Therefore in normalized form, X.« X^. Thus A and B are similar on X. QED Although the complexities for the two inputs (x- and x^) are the same in each program, the magnitude of this complexity for the two programs is, in general, different. Thus x.^.Xj and Xj^«gX2 ^^ ^^^ imply that C(A,Xj^) = C(B,Xj^). Similarity between two programs is preserved by taking subsets of the original input set, and by Intersection of different input sets which induce similarity. Theorem 2 ; if A and B are similar on X and also on Y, they are similar on Z C X and on X n Y. Proof: (Subset) Let [x. | = n. Define Z =Z D X , VX, ex.. Then i A n i= u z = u (z n X.) = z n(u x.) = z n x = z =1 ^ 1=1 ^ i=i ^ ■58- ALsoj for i ^ j, z.n z^ = (z n xp n (z n x^) z n (x.n Xj) = z n = Eliminating any Z^= 0, Z^= [Z^] is in normal form. Since X^= Xg, Z^= Z , Therefore A and B are similar on Z. (Intersection) XflY ^. Using the first part of the proof, A and B are similar on X fl Y. QED Absolute Similarity Certain pairs of programs may be similar on all valid input sets. We have the following definition: Definition : A and B are absolutely similar iff A and B are similar on all valid input sets X. Lemma 2 : If A and B are similar on the maximal valid input set X, they are absolutely similar. Proof: All valid input sets are subsets of the maximal valid input set. By theorem 2, since A and B are similar on the maximal input set, they are similar on all valid input sets. Thus A and B are absolutely similar. QED -59- Leirrma 3 : If A and B are absolutely similar, and if A and B are similar on X and on Y, they are similar on X U Y, Proof: The union of two valid input sets is also a valid input set. By hypothesis, A and B are similar on all valid input sets, QED Homomorphism We define the relational operators < and > for single A A inputs and input classes. Definition ; For x^^X2 valid inputs to A, x > x iff C(A,x^) > C(A,X2) and x^<^X2 iff C(A,x^) < C(A,x ), For X., X. equivalence classes of A, X^ >,X. iff i J i A J C(A,X ) > C(A,X.) and X <-X. iff C(A,X,) < C(A,XJ. Similarity tells us that for B similar to A, x =.x iff Xj^-gX^. It also implies that x^^/^x^ iff ^^^ x^. We cannot say that x-<.x implies x < x^j nor can we establish any other ordering relation on the complexities of inputs. To do this, we need to define another relation on programs with the same input set which will tell us something more about the relative magnitudes of the equivalence class complexities. This leads to the following definition: -60- Deflnltlon : Suppose A and B are similar on X and we order the equivalence class complexities C(A,X.) and C(BjX ) ^ J in strictly increasing order (strictly increasing because X and X^ are in normal form) to form two n-tuples (n= |X | ) : (C(A,X^), C(A,X2), ..., C(A,X^)) (C(B,X^). C(B,Xp, ..., C(B,X^)) Because X^= X„ we know that: A B m^e\) (3X^e Xg) IX^= X'] (VX^e Xg) (3XjG X^) [X^= Xj Then A and B are homomorphic on X iff (TI S i s: n) [X =: X* ] The main property of the homomorphic relation^ that the order of complexity is preserved in homomorphic programs, is shown in the following theorem: Theorem 3 : A and B are homomorphic on X iff (Vx.^x^e X) [x^ relop^ X2<=> x^ relop ^ x^] where relop e {>,=,<} and is the same in both cases. "61 Proof: (=>) Let Xj^gX , X2eX.. Suppose C(A,X.) is in the i position of its ordered n-tuple (as above) and G(A,X ) is in the j position. By homomorphism, C(B,X ) and C(B,X ) are in the i — and j — positions of their n-tuple. Then C(A,X^) relop C(A,X,) iff C(B,X ) re lop C(B,X.) J J C(A,Xj^) relop c(A,X2) iff C(B,x ) relop C(B,k ) X- relop X iff x relop x where relop is the same operator in all cases. (<?=) By hypothesis, (Vx^,x^ eX) [at relop^ x^ iff ^1 £ii2Eg ^2^' ^" particular, ^l'^A^2 ^^^ ^l'^B^2^ ^° ^^ theorem 1, A and B are similar on X, Now assume that in the ordered n-tuples for C(A,X^) and C(B,Xp, (31) [X^?^ X^]. Let i be the smallest index for which this is true. Suppose the element corresponding to C(A,X ) is C(B,X ). We then have: (C(A,Xj^), C(A,X2). ..., C(A,Xj,) ...) (C(B,X^), C(B,X2), .... C(B,X^) ...) Since i is the smallest index, then X, could not have occurred within the first 1-1 complexities C(A,K ), k s i-1. Therefore, C(A,X.) > C(A,X.). Similarly, C(B,X ) > G(B,X.). If x e X., J *' X- J L 1. K^e X,, x^< X but X > X . Contradiction! Then our assumption that X 7^ X' was wrong. Thus A and B are homomorphic on X. QEI) The homomorphism relation gives us the information we -62- need to determine the relative magnitudes of the equivalence class complexities of two programs. To see if homomorphism holds^ we need only examine the two sets of complexity equiva- lence classes and the associated complexities. If |X | « |x|^ the number of objects we will have to examine is small compared to the total number of inputs. As with similarity, homomorphism is preserved by subset and intersection of input sets: Theorem 4 : If A and B are homomorphic on X and on Y, they are homomorphic on Z Q X and on X n Y. Proof : (Subset) By theorem 1, A and B are similar on Z. We can order the equivalence class complexities of A and B on Z: (C(A,Z^), C(A,Z2), ..-, C(A,Z^)) (CCB.Z^), C(B,Z^), ..., C(B,Z^)) where Z.=X.n Z and Z'=X'n Z as in the proof of theorem 2. Since X.= X'j then Z.= t\, VZ.e Z (= 'z ) /. A and B are homomorphic on Z. (Intersection) XflY cX. Using the first part of this proof J A and B are homomorphic on X Pl Y. QED -63- Homomorphism and Complexity Limits In Chapter III^ we Introduced the notion of maximum and minimum complexity on a set of Inputs. We noted that these quantities bound the resource usage of a program on a particular input set. Here, we formally define these two quantities and also two others. Definition ; Given a program A with input set X and X^ in normal form, we can define the following quantities: X^^(A) = that X, for which C(A,X,) = C „ (A,X) m*ix 1 t max X^^^(A) = that X^ for which C(A,X^) = C ^^CA^X) ^max ^^^ \ln ^^^ unique by the normal form condition. They tell us which inputs will consume the greatest amount of the resource being measured and which inputs will consume the least. These two quantities are preserved by homomorphism: Lemma 4 : If A and B are homomorphlc on X, then ■■■ ■''■■mW' ■;-7"!i. t: ^mw] •64- Buferby Proof : SuppoM i„^^(A.) - X^. Tli«n (VX^eX^, V l^^^l'^A^j^ '')-■: s :y^.:^iir (^jS Xg, Xj?«X^)lX^'^ Xj] ;l.i-^,v -■•••■i" .•.\i,(^)-^, Similarly, for X^^^CA) - X^^<B). QED We also state, without proof, the following which relates complexity limits to subMjtts of inpttt sets: ,X) and ^ if Z c X, thai C^,(A,2) s Thus c _ and C for the maximal valid input set limit the corresponding quantities for all other valid input sets. «:•; «. =J-. -65- Absolute Homomorphlsm Analagous to absolute similarity, we can define two programs to be absolutely homomorphlc if they are homomorphic on all valid input sets. Results corresponding to lemmas 2 and 3 can be shown for absolute homomorphism. Isomorphism We now define one last equivalence relation between programs with the same input set; this relation is stronger than homomorphism. Definition : A and B are isomorphic on X iff they are similar on X and (VX.e\)[C(A,X.) = C(B,X^)] Isomorphism is a special case of homomorphism:; the complexity associated with any equivalence class is the sa-u-e for both programs. As we would expect, isomorphism is preserved by subset and intersection of input sets; however^ it is also preserved by union of input sets. Theorem 5 : If A and B are isomorphic on X and on Y, they are also isomorphic on Z c X, X fl Y^ and X U Y. Proof : (Subset) By theorem 4, A and B are hociomorphic on Z. (VZ^G Z^) [C(A,Z,) = C(A,X^) = C(B,X.) = C(B,Z^)] W^---M-^-'''^" '^'^ '■w-^- T ■ ■■:■■ v^-:-iu 'bsj.:^-'y' '■■ ^.- ^v^Mi.: (Intersection) Follows from etdiset proof. (Union) Let Z « X U t» First iffetttfcist show U { X^U Y. I X^.^Y 3 Similarly, 2^- Z^j^U Z^\J Z^y By hypothesis, X - X^, Y « Y (VX^,Yj)[C(A,X^) . C(»,;f^) f <?(4,3Cj) * C(»^Yj) ••• \l- Si •~* 2^ - Zb2 since X^^l^.-r>^-^Tj,, 1^3- J^3,.. -^ - r>.3 C(A,Zj) C(A,X^), Z^« X^ ^^^^^.j^b;.. . ^. . /^ir-'-^v- n --^^. ^. teis i^ ^ -^-.o::-/': t« (:5^<^d^^E> ^|!E:2S. •67- C(B,Z. ) = f C(BjX.), Z = X. ^ J ILL ^ C(B,Y.), Z^ = Y. (Note: if Z.= X.U Y., C(A,X^) = C(A,Y. ) and C(B,X.) = C(B,Y.)) But by hypothesis, C(A,X^) = C(B,X.) and C(A,Y. ) = C(B,Y, ) Therefore, C(A,Z^) = C(B,Zj, ^Z^e Z^. Thus A and B are isomorphic on X U Y. QED Isomorphism not only preserves X and X , but also max min *^max^ ^min^ ^"^ C(A,X); we state the following easy leimna without proof. L^maa^: if A and B are isomorphic on X, then C(AjX) = C(B,X) if the methods used in selecting tlie inputs to A and B (i.e., Pr(X^)) are the same. We will return to isomorphism in the next section when we discuss concatenation of programs. 4. Concatenation We will now investigate the complexity properties of programs which may be combined or concatenated to from larger programs. By the concatenation of two programs A and B, we mean the program which is formed by appending T; to the eud jf A, -68- so that when the locus of execution reaches the enu of A^ it will enter B, We will assume that A places the outputs of its computation into certain registers and that these same registers are used by B as inputs. B is not requred to use ail of A's outputs as inputs: however^ B cannot need more inputs than A can supply. We will say that A is l/O- compatible to B if this restriction is obeyed. We will also assume that neither A or B is changed by the concatenation of B onto A (which will be denoted by *'A«b"). We run into at least one trouble spot: If A finishes execution by halting somewhere in the middle. To continue with the execution of B, we would need to change this HALT instruction into a BRANCH to the end of A, This modification would probably change A*s complexity with respect to certain inputs. To avoid this difficulty, we will assume that all programs teniiinate by executing their last instruction. Thus we rnay perform cunca- tenation without changing instructions in either r i ogram. If we wish to study the complexity of A»B for an input set Xj the inputs to B will have to be valid haltin- inputs. Therefore, A(X), the set of inputs to B, will always be a ^^alid input set. Given this fact, the complexity of A»B for any input X can be determined by linearity: C(A.B,x) - C(A,x) + C(B,A(x)) -69- Compatlbllity We now place another restriction on the concatenation of programs which will enable us to prove some properties on the complexity of concatenation. This restriction will be defined in two stages as follows: Definition : Let A be I/O- compatible to B and for X a valid input set to A, A(X) = Y is a valid input set to B. Then A is X^ - compatible to B iff for X^e X^ (in normal form), there exists Y.e Y_ (in normal form) such that A(XJ = F e Y J 15 i i j' X^- compatibility tells us that a set of inputs (X ) which, by definition have the same complexity for A (C(A,X )) will be transformed into a set of inputs (F ) for B which will all have the identical complexity - C(B,Y.). We now extend this relation to all equivalence classes of X: Definition ; A is X- compatible to B iff A is X,-con^atible to B for all X^e X^ (in normal form). If A is X-compatible to B, it is easy to see that for x-,x^e X, ''1V2 => *rA.B^2 However the converse is not necessarily true. If x-t^.x and A(Xj^) T^g A(X2), it may still be that \=^,J>^2- ^^ theorem 1, -70- we conclude that A and A»B are not necessarily similar on X. Compatibility is preserved by several operations on input sets. We state the following two theorems without Including the proofs. Theorem 6 ; If A is X-compatible to B and also Y- compatible to B, and if Z ^ x, A is Z- compatible and X Y- com- patible to B. Theorem 7 ; If A is X-compatible to B and also Z- compatible to B, and if for A(X. ) c y. and A(Z. ) ^ T., X =.Z, => Y = T,j then A is X U Z-compatible to B. j[ A 1 1 B 1 In the case of theorem 7, we need the additional restriction that (X.^.^ => Y,= T. ) because if two equivalence classes (X.,Z ) must be combined in the normal form of (X U Z) as a result of having the same complexity 0^j^A^,)f the images (Y.jT ) of these classes under A must also have the same complexity (Y ,%T.) so that A(X.U Z.) ^ Y, U T^ . X JD X X X XX Compatibility and Isomorphism To conclude the section on concatenation, we discuss some relationships between compatibility and isomorphism. We would like to see under what conditions isomorphic programs can be concatenated to yield programs which are still isomorphic. We first show that isomorphism is preserved by the concatenation of the isomorphic programs to a program which is compatible to -71- both: Theorem 8 : If A is Y-compatible to B and to G^ and if B and C are isomorphic on X = A(Y)^ then A»B and A»C are isomorphic on Y. Proof: Let D = A^B^ E = A»C, We need to show that Y - Y^ and (VY. gY^) [C(D, Y. ) = C(E,Y.)], Y^ is composed of two u h 1 D 1 1 D subsets : V ^\'\\ (^j^v^Vd^j^ ^ U[Y.UYj Y.=^Yj^ } = Yd1^^D2 Similarly, Y^= Y^^U Y^^ Since C(B,X^) = C(C,X ), VX.e IL, it must be that \r "^El ^""^ "^02= ^2- Therefore, Y^= Y^ Then (VY.e Y^^), C(D,Y. ) = (by linearity) C(A,Y,) + C(B,A(Y.)) = (by isomorphism) C(A,Y.) + C(C,A(Y.)) = (by linearity) C(E,Y.) .'. A«B and A«C are isomorphic on Y. QED -72- Since A«B and A»C are isomorphic, we can continue the concatenation if we can find a program D which is Z-compatible to A»B and A-C and where D(Z) c Y. Then D.A'B and D'A«C will be isomorphic on Z. We now show the conditions under which the concatena- tion of pairs of isomorphic programs results in programs which are also isomorphic. Theorem 9 : Suppose A and B are isomorphic on X, A is X-compatible to C, B is X-compatible to D, C and D are isomorphic on Y = A(X) U B(X), Then A«C and B*D are isomorphic on X iff (VX.eX )OY,e Y )[A(XJ, B(X ) cy.] 1- A J c I 1 J Proof : (<^) Let E ~ A»C, F = B»D. Then U [ X^U X. 1 X^=^X^ } = X^^U X^2 Similarly, \= \^\J X^^ Since A(X^), B(X^) c y and C and D are isomorphic on Y, C(C,A(X.)) = C(C,Y.) = C(D,Y.) = C(D,B(X )). Also, C(A,X ) = C(B,X ), VX e X Thus, C(E,X. ) = C(F,X.), VX . ^ i- 1 /i 1^ 1 i -73- •■• ^r ^1, V ^2 ^"^ '^^"^ V \ Then (VX^eXg), C(E,Xj^) = (by linearity) C(A,X^) + C(C,A(X^)) = (by isomorphism) C(B,X^) + C(C,A(X^)) = (by hypothesis) C(B,X^) + C(C,Y.) = (by isomorphism) C(B,Xj^) + C(D,Yj) = (by hypothesis) C(B,X^) + C(D,B(X^)) = (by linearity) C(F,X^) A»C and B»D are isomorphic on X. (=>) Given A(X^) £ Y , B(X ) C Yj^, we want to show that Y = Y^, For X^e X^, C(E,X^) = C(F,xp. By linearity, C(A,X^) + C(C,A(X^)) = C(B,X^) + C(D,B(X^)). But C(A,Xj^) = C(B,Xj^) so we must have that C(C,A(X )) = C(D,B(X^)); or C(C,Y ) = C(D,Y^). But since C and D are isomorphic on Y, then Y = Y_ (in normal form). Therefore, Yj= Y^^. QED 5, Functional Equivalence It Is often the case that we wish to examine two programs which represent different algorithms for the same function. The programs compute the same output when given the same input from a specified input set; however, the method -74- (algorithm) used to compute the result is not the same. This situation often arises when we wish to determine which version of a particular subroutine or program we should use. All versions represent (hopefully!) the same function, but one version may use less resources than another. Program equivalence may also arise in the area of simulation. If one program is simulating another^ and if the first program is also producing the same output as the second, then the programs are equivalent. Equivalence is defined here in terms of similar func- tional behavior on a specified input set. Output values are defined as transformations on input values. If output variables are not also inputs, their values must be expressable in terms of the inputs. Definition: A and B are equivalent on X iff (Vx G X)[A(x) = B(x)] It is easy to see that equivalence is closed under subset, union, and intersection: if A and B are equivalent on X and on Y, they are equivalent on Z £ X, X Y, and X U Y. Equiva- lence and concatenation are related by the following lemma: Lemma 7 : If A and B are equivalent on X, C and D equivalent on Y where A(X) c y; and if A, B are l/O- compatible to C, D then A»C, A»D, B«C, B»D are equivalent on X, -75- Proof: By l/0-compatlblllty restriction, A»C, etc. may be correctly formed. Now for xeX, A(x) = B(x) = y. Since yeY, C(y) = D(y). Therefore, A.C(x) = B*D(x) and A.C and B.D are equivalent on X. Similarly for the other cases. qed To conclude this chapter^ we present the following theorem which relates isomorphism, compatibility and equivalence: Theorem 10 ; Suppose A and B are isomorphic and equivalent on X, A is X*compatible to C, B is X-compatible to D, C and D isomorphic on Y ^ A(X) ^ B(X) (since A and B equivalent). Then A«C and B»D are isomorphic on X. Proof t We look at theorem 9. Since A(x) = B(x), Vx G X, A(X^) = B(X^), VX^e X^. Since A is X-compatible to C, A(X^) C Y , Ye Y^. But by the isomorphism of C and D on Y, Ye Yjj. Then B(X^) c Y . Therefore, A*C and B*D are isomor- phic on X. QED If C and D are equivalent on Y in addition to being isomorphic, we can use lemma 7 to conclude that A»C and B*D are isomorphic and equivalent on X« -76- Chapter VI. Conclusions and Suggestions for Further Study Conclusions We have developed a general theory of computational complexity for computer programs. We have looked at complexity from the viewpoint of resource usage and regarded the use of different resources as different measures of the complexity of a program. Many complexity measures fit into our theory, the only requirement being that the usage of the associated resource obey the linearity principle. Our theory has been based upon observing the behavior of a program on a valid set of inputs. We have also relied extensively on an equation representation of the transformations which a program applies to its inputs. We have attempted to justify the use of finite input sets by noting that real pro- grams, running on real computers, are able to accept and manipulate only a finite number of distinct input values, due to software and hardware limitations. In addition, most pro- grams actually process only a subset of all possible input values. Our methods were shown to be valid for programs with a large number of programming linguistic constructs and with several different input schemes. The complexity analysis of a program produced a set of complexity equivalence classes and a corresponding set of class complexities. We have noted that most programs do not -77- treat every input value differently, and therefore the number of equivalence classes will generally be smaller than the number of possible inputs. Thus, these two sets give a relatively compact representation of the complexity information for a program operating on a given input set. These sets immediately led to some complexity parameters for the program: 1. C(A,X) - the expected complexity value on the set X 2. C^^^(A,X) - the maximum complexity on the set X ^' "^roax^^^ " ^^^^^ inputs which result in complexity C (A,X) ^- C^^^(A,X) - the minimum complexity on the set X ^' \in^^^ " ^^^^® inputs which result in complexity C (A,X) ^max^^^^^ ^^^ ^min^^^^^ bound the resource usage of program A and tell how much of this resource A can possibly use and how much it must use to process inputs from set X. Our basic purpose has been to develop some theoretical tools for studying the difficulty of computing functions by observing the program implementations of these functions. While these techniques will work for any program of the tjrpes described, the necessary computations will become unmanageable if the program equation is complex or if the number of complexity equivalence classes is large. Thus, one could not expect to sit down and find the equation and equivalence classes of a PL/l compiler, just as one would be hard-pressed to prove that such a compiler is "correct*'. Our techniques will probably be most valuable in the analysis of small programs and also -78- in deciding which version of a particular program will be most suitable for use; suitable in the sense of using the least resources over a particular set of inputs^ where we may wish to minimize C(A,X), C ^ (A,X), or C , (A,X). max min Programmers and systems analysts are often faced with this latter problem, particularly in a large programming system such as a language translator or operating system which is modularized and which has its basic components frequently replaced as the system is up-graded. The complexity analysis techniques allow different versions of program modules to be compared, perhaps in one case on the basis of maximum resource usage, in another with regard to average resource usage, in a third with respect to some combination of complexity parameters. Areas for Further Study We have used the concept of a program equation for much of our work. This equation is independent of a study of complexity. It gives a concise algebraic formulation of a program or algorithm. It is also valid on an infinite input set as long as all elements in this set are halting inputs for the program in question. The equation brings to light the transformational characteristics of a program. It should be useful in the study of other aspects of programs and programming languages, such as program semantics and program correctness. -79- A subject which we have not examined but which is important is the use of space as a complexity measure. The use of space did not follow the linearity principle. An analagous constraint for space and its related measures would have to be devised to analyze the complexity of programs with respect to these resources. We have not discussed the effects of transformations of the program on the complexity. For example, suppose we make a well-defined modification to program A with input set X. Is there a well-defined effect on X., C (A,X), C , (A,X)? A max min Cooper's work on graph transformations [8] may be useful here. We have defined three equivalence relations between programs with the same input set. There may be other relations, intermediate in strength between similarity and isomorphism which reflect other programming situations. We have mentioned that it is advantageous for |X| » |X^1. In this case, X^ and { C(A,X^) ] X^e X^} give us a more economical representation of the complexity informa- tion for A than if we simply looked at all x in X. However, we have not explored the relationship between the relative size of X^ and the nature of A itself. Are there certain conditions for which we get this economical representation? -80- Appendix - Mathematical Notation Sets We make use of the notion of a set and various opera- tions upon it. A set is an unordered collection of objects and is named by a capital letter. The elements of a set are enclosed in braces and separated by commas. A subset of a given set is another set containing allj some^ or none of the elements of the original set. If Z is a subset of X^ we write Z C X. If a subset contains no elements^ it is called the empty set and denoted by 0. The size of a set X is written |x| and is simply the number of elements in X. The union of the sets X and Y^ denoted X U Y, is a set containing those elements which are in either X or Y or both. The intersection of sets X and Y^ denoted X H Y^ is a set containing those elements which are in both X and Y. We denote membership in a set by the symbol e. Thus, a e { a^b }. Similarly^ c £ [ a,b }. A set may be specified by describing the conditions for membership in the set rather than listing all of the members. We use the notation X = { X I "conditions" ) This may be read 'X is the set of all objects x such that the -81- condttions are true". Thus the set Y = [ X I xeX^ and xgXg } describes Y as the intersection of X- and X« Ordered Pairs, Cross Products An ordered pair, denoted (x,y), is an object with two components. The order of the components is significant: (x,y) is distinct from (y,x) unless x = y, A set of ordered pairs can be formed from sets of single objects by the cross product operator. The cross pro- duct of the sets X and Y, denoted Xx^ is defined as follows: XxY « { (x,y) I xeX and yeY J Quantifiers We use two logical quantifiers in our notation. The universal quantifier, denoted V, may be read "for all". It is used to qualify the statement following it. Thus, (V^ e X)]x ^ y] means "for all x in X, x ^ y". The existential quantifier, 3, may be read "there exists". The statement (3x G X)[x 5 y] -82- means "there exists an x in X such that x ^ y". Quantifiers may be grouped in a series to form more complex logical statements. We might have (Vx e X)(ay e Y)[x ^ y] which states that "for all x in X^ there exists a y in Y such that X ^ y". Functional Composition The composition of functions f and g, denoted f«g, is another function which transforms the domain of g into the range of f. Thus if g(x) = y and f (y) = 2, f»g(x) = z. Composi- tion may be continued for any number of functions. If a function f is composed with itself i times, we may abbreviate this as f . Implication and Equivalence If the truth of statement A implies the truth of statement B, we write A => B This may also be read "if A then B", Similarly if B implies A, we write B => A •83- If A and B laply aadi othttt, thay art said to hB aquivalaiit and va vrlta /^? ■ ::>.'Tl^ m ■ ■ ^SiSa^- r*^/^# vv. a^' t:r^, -^iv-;:-^#^3f*^^.*^^ ;^^^".. Irl^ ?:''>;H ^ i^^ ,;" :V/ .■ p^ i- \ •= . ^ ■ '^ ^■' . 15 ^^^^'-^ iJ^jad:>£jT ;^\^l^alc^fi3r> rsv^ol-^^^'-'^^^^ii- Jo^-^m^"-' Vb cam aUo irrlta aq^vitlaiMa aa iiii«i ^^'^ l0 an abbreviation for '^f and only If '^ i . ■.,.■■.. ■ ^' ^ ii'*'^' m -84- References 1. HartmaniSj J. , and j/ E. Hopcroft, "An Overview of the Theory of Computational Complexity*'^ Technical Report No. 70-59, Department of Computer Science, Cornell University, April 1970. (See also JACM 18(3), July 1971, for a later version of this report). 2. Landin, P. J., ''The Mechanical Evaluation of Expressions", Computer Journal 6, 4 (January 1964) pp. 308-320. 3. Blum, M. , "A Machine Independent Theory of the Complexity of Recursive Functions", JACM 14 (1967) pp. 322-336. 4. Meyer, A. R. , and D. M. Ritchie, '*rhe Complexity of LOOP Programs", Proceedings of the 22— National ACM Conference . (1967), pp. 465-469. 5. Ramamoorthy, C. V., "Discrete Markov Analysis of Computer Programs", Proceedings of 20 — National ACM Conference . (1965), pp. 386-392. 6. Zeiger, H. P., 'iForroal Models of Some Features of Programming Languages", Proceedings of the 3 — Annual Princeton Conference on Information Science and Systems , (1969), pp. 425-429. W'^^'m ■if i 7. DrakA, A., Fundaaantala of Applied Probability Theory, MW}r«w-Hlll Book Conpany (1967), N«r York, 8. Cooptr, D. C, "Bom TransfonMtlou and Standard Foms of ^aphs, with Applications to Gooputar Frograms", In Ifcchlna Intalllaanca 2, Dala and tfilcfala («d. ) iMrloan KlsavUr Publishing Coapany, Inc., (1968), Mw Tork. TINrT.A.q.qTFTFT-l Security Classification DOCUMENT CONTROL DATA - R&D (Smcurity ctaamiticmtion o/ titt; body of mbmtrmct mnd indexing mxnotmUon mu9t b« «nr*red when the ovmratt report i» ciaMsitimd) \. ORIGINATING ACTlvrTY (Corporate author) Massachusetts Institute o£ Technology- Project MAC Za. REPORT SECURITY CLASSIFICATION UNCLASSIFIED 2b. GROUP None 3. HtPORT TITLE Complexity Measures for Programming Languages 4. DESCRIPTIVE NOTES (Type of report and inclueiv Technical Memorandum 5. AUTHOR(S) (Last name, tirat nmne, initial) Goodman, Leonard I. 6. REPORT DATE September 1971 7«. TOTAL NO. OF PAGES 86 7b. NO. OF REFS 0a. CONTRACT OR GRANT NO. Nonr-4102(01) b. PROJECT NO. 9a. ORIGINATOR'S REPORT NUMBERIS) TM-17 9b. OTHER REPORT NOtS) (Any other number* that may be aeeigned thie report) 10. AVAILABILITY/LIMITATION NOTICES Distribution o£ this document is unlimited. t1. SUPPLEMENTARY NOTES None 12. SPONSORING MILITARY ACTIVITY Advanced Research Projects Agency 3D-200 Pentagon Washington, D.C> 20301 13. ABSTRACT A theory of complexity is developed for algorithms implemented in typical prograimning languages. The complexity of a program may be interpreted in many ways; a method for measuring a specific type of complexity is a complexity measure -- some function of the amount of a particular resource used by a program in processing an input. After the complexity of the basic program elements is determined, program complexity is analyzed with respect to single inputs and then with respect to finite sets of legiti- mate halting inputs. A program equation is developed to aid in the complexity analysis. Using this equation, an input set is partitioned into classes of constant complexity. Several equivalence relations are defined, relating different programs by their complex- ity. Complexity is also discussed in terms of concatenation and functional equivalence of program. 14. KEY WORDS Computational Complexity Program Resource Usage Complexity Measures Programming Languages Program Equations Program Equivalence Relations DD/nSei. 1473 (M.I.T.) Security Classification